#!/usr/bin/python3
import sys


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


try:
    t = int(input())
    if t < 1 or t > 50:
        sys.exit(0)
    for x in range(t):
        n = int(input())
        result = 0
        for n1 in range(1, n + 1):
            result += n - gcd(n1, n)
        print('Case #{}: {}'.format(x + 1, result))
except ValueError:
    pass
except EOFError:
    pass
except MemoryError:
    pass
